package LearnDataStructure.c_树结构.例题;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-17 20:50
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 以二叉树的
 * 中序遍历
 * 后序遍历
 * 这两种作为演示
 */
public class m_根据两种遍历结果恢复tree {

    public static void main(String[] args) {
        int[] zhongXu = {3, 2, 1, 4, 5, 7, 6};
        int[] houXu = {3, 1, 2, 5, 6, 7, 4};
        m_根据两种遍历结果恢复tree test = new m_根据两种遍历结果恢复tree();
        TreeNode tree = test.createTree(zhongXu, houXu);
        List<List<TreeNode>> lists = test.levelOrder(tree);
        for (List<TreeNode> list : lists) {
            for (TreeNode element : list) {
                System.out.print(element.val + " ");
            }
            System.out.println();
        }
    }

    /**
     * 使用递归，创建子树
     * @param zhongXU
     * @param houXU
     * @return
     */
    public TreeNode createTree(int[] zhongXU, int[] houXU) {
        int size = zhongXU.length;
        if (size == 1) {//递归出口
            return new TreeNode(zhongXU[0]);
        }
        //利用后序遍历特点，最后一个element就是root
        int rootValue = houXU[size - 1];
        int indexInZhongXU = -1;
        for (int i = 0; i < size; i++) {///寻找中序遍历中的root的索引
            if (zhongXU[i] == rootValue) {
                indexInZhongXU = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootValue);

        /*
        根据两种遍历的结果
        分开左右子树
        这里是创建子树的核心
         */
        int[] zhongXuLeftElements = new int[indexInZhongXU];//实际索引最大为indexInZhongXU-1
        int[] houXuLeftElements = new int[indexInZhongXU];
        int[] zhongXURightElements = new int[size - 1 - indexInZhongXU];//从索引角度，把左边一半减去，剩下的数量，当成新数组的length
        int[] houXURightElements = new int[size - 1 - indexInZhongXU];

        /*
        后序遍历
        中序遍历
        在root视角看，都是先遍历完root.left，再去进行别的
        同时开始的话，当中序遍历完root.left，此时后序遍历也完成了root.left的遍历！
         */
        /*
        根据两种遍历的结果
        分开左右子树
        这里是创建子树的核心
         */
        //复制左子树
        for (int i = 0; i < zhongXuLeftElements.length; i++) {
            zhongXuLeftElements[i] = zhongXU[i];
            houXuLeftElements[i] = houXU[i];//不懂的话，看上面的注释
        }
        /*
        根据两种遍历的结果
        分开左右子树
        这里是创建子树的核心
         */
        //复制右子树
        for (int i = 0; i < zhongXURightElements.length; i++) {
            zhongXURightElements[i] = zhongXU[indexInZhongXU + 1 + i];//+1是跳过root
            houXURightElements[i] = houXU[indexInZhongXU + i];
        }
        //递归
        root.left = createTree(zhongXuLeftElements, houXuLeftElements);
        root.right = createTree(zhongXURightElements, houXURightElements);

        return root;
    }

    public List<List<TreeNode>> levelOrder(TreeNode root) {
        List<List<TreeNode>> result = new ArrayList<List<TreeNode>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //初始化
        queue.add(root);
        TreeNode last = root;
        TreeNode next = null;

        //一定有第一行;为第一行做准备
        List<TreeNode> currentLine = new ArrayList<TreeNode>();
        // firstLine.add(root);这里不添加
        result.add(currentLine);//先加入空行，后面会填入数据

        while (!queue.isEmpty()) {
            TreeNode peek = queue.peek();//peek是待出列元素
            if (peek.left != null) {
                queue.add(peek.left);
                next = peek.left;
            }
            if (peek.right != null) {
                queue.add(peek.right);
                next = peek.right;
            }
            // if (peek.children != null) {
            //     for (TreeNode child : peek.children) {
            //         queue.add(child);
            //         next = child;//移动指针；最终next会指向最后一个孩子
            //     }
            // }
            //队列弹出首元素
            TreeNode currentFirstElement = queue.poll();
            //代表当前的行的列表currentLine,此时添加出列的元素
            currentLine.add(currentFirstElement);
            if (peek == last && !queue.isEmpty()) {//如果弹出元素就是last指针指向的元素，且队列不为空
                currentLine = new ArrayList<TreeNode>();
                result.add(currentLine);//先加入空行，后面会填入数据
                last = next;
            }
        }
        return result;
    }
    
    static class TreeNode {
        public Integer val;
        public TreeNode left = null;
        public TreeNode right = null;
        public TreeNode(Integer val) {
            this.val = val;
        }
    }
}
